A database is a collection of stored data that is logically related and that is accessible by one or more users or applications. A popular type of database is the relational database management system (RDBMS), which includes relational tables, also referred to as relations, made up of rows and columns (also referred to as tuples and attributes). Each row represents an occurrence of an entity defined by a table, with an entity being a person, place, thing, or other object about which the table contains information.
One of the goals of a database management system is to optimize the performance of queries for access and manipulation of data stored in the database. Given a target environment, an optimal query plan is selected, with the optimal query plan being the one with the lowest cost (e.g., response time) as determined by an optimizer. The response time is the amount of time it takes to complete the execution of a query on a given system.
In massively parallel processing (MPP) systems, the processing costs for performing parallel joins can become undesirable. As is understood, a join comprises a structured query language (SQL) operation that combines records from two or more tables. Efficient parallel joins are critical to the performance of parallel database systems.
Consider a frequently used mechanism for executing a parallel join on two relations R and S on R.a and S.b (where “a” and “b” are respective columns of the relations R and S). Assume neither relation R nor S has been partitioned by its respective join attribute. A relation may be divided among a plurality of processing modules in the MPP system. Such a mechanism is referred to herein as partitioning. Typically, a relation is partitioned on a primary index, e.g., one or more columns by hashing the rows on the primary index and distributing the rows to a particular processing module based on the primary index hash value. First, rows from R and S are redistributed according to a hash value on the respective join attribute “a” and “b” so that rows from R and S that match on R.a=S.b are redistributed to common processing modules. Each processing module then joins the rows of R and S that have been hash redistributed to the processing module.
In conventional parallel DBMSs, rows are statically redistributed to processing modules based on a pre-configured hash value-to-processing module mapping table. In practice, often the hash value-to-processing module mapping is done in two steps: a prefix of the hash value (for example, the first half bits of the hash value) is taken to map the hash value to an integer referred to as a hash bucket, and then the hash bucket is mapped to a particular processing module. Thus, rows are redistributed to processing modules solely on the hash value and regardless of the number of rows that are redistributed across the system. Sometimes, such a mechanism results in a high processing cost that disadvantageously impacts the overall processing efficiency.